#define _CRT_SECURE_NO_WARNINGS 1

class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum()
    { }

    void insert(string key, int val)
    {
        int gap = val - _wordValMap[key];
        _wordValMap[key] = val;

        size_t n = key.size();
        for (size_t i = n; i > 0; --i)
        {
            _prefixSumMap[key.substr(0, i)] += gap;
        }
    }

    int sum(string prefix)
    {
        return _prefixSumMap[prefix];
    }

private:
    std::unordered_map<std::string, int> _wordValMap;
    std::unordered_map<std::string, int> _prefixSumMap;
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */